package hotLeetcode;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class H11Leetcode239 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int x = 0;
        int[] result = new int[len - k + 1];
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                int index = j,max = Integer.MIN_VALUE;
                while (index < j + k && index < len) {
                    max = Math.max(max, nums[index++]);
                }
                if (x < result.length) {

                    result[x] = max;
                    x++;
                }

            }
        }
        return result;

    }


    //滑动窗口
    public int[] maxSlidingWindow2(int[] nums, int k) {
        int len = nums.length;
        int[] result = new int[len - k + 1];
        for (int left = 0; left < len; left++) {
            int right = left + k, max = Integer.MIN_VALUE;
            int index = left;
            while (index < right && index < len) {
                max = Math.max(max, nums[index++]);
            }
            if (left < result.length) {
                result[left] = max;
            }
        }


        return result;

    }

    //双端队列
    public int[] maxSlidingWindow3(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>(); // 双端队列，存储数组元素的索引

        for (int i = 0; i < n; i++) {
            // 如果队列的头部元素已经不在当前窗口中了，就移除它
            if (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }

            // 保持队列的单调性，移除所有小于当前元素的元素
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            // 将当前元素的索引加入队列
            deque.offer(i);

            // 当窗口完全形成时，记录最大值
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peek()];
            }
        }

        return result;
    }



    public static void main(String[] args) {
        int[] arr = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        H11Leetcode239 h11Leetcode239 = new H11Leetcode239();
        System.out.println(Arrays.toString(h11Leetcode239.maxSlidingWindow3(arr, k)));
    }
}
